package previous.Test_0319;

import java.math.BigInteger;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //地图中最高点
    public int[][] highestPeak(int[][] isWater) {
        int m=isWater.length;
        int n=isWater[0].length;
        int[][] w=new int[m][n];
        Queue<int[]> q=new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                w[i][j]=-1;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(isWater[i][j]==1){
                    q.add(new int[]{i,j});
                    w[i][j]=0;
                }
            }
        }
        while(!q.isEmpty()){
            int[] t=q.poll();
            int a=t[0];
            int b=t[1];
            int[] dx={0,0,1,-1};
            int[] dy={1,-1,0,0};
            for (int k = 0; k < 4; k++) {
                int x=dx[k]+a;
                int y=dy[k]+b;
                if(x>=0 && x<m && y>=0 && y<n && w[x][y]==-1){
                    q.add(new int[]{x,y});
                    w[x][y]=w[a][b]+1;
                }
            }
        }
        return w;
    }
    //柠檬找水
    //5元，不用找；
    //10元，如果有5元找5元；
    //20元找15，分别为5，5,5；10,5
    public boolean lemonadeChange(int[] bills) {
          int five=0;
          int ten=0;
          int twenty=0;
        for (int i = 0; i < bills.length; i++) {
            if(bills[i]==5) five++;
            else if(bills[i]==10){
                if(five!=0) {
                    five--;
                    ten++;
                }else {
                    return false;
                }
            }else{
                if(five!=0 && ten!=0){
                    five--;
                    ten--;
                    twenty++;
                }else if(five>=3){
                    five-=3;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
    //地图分析
    public int maxDistance(int[][] grid) {
          int m= grid.length;
          int n= grid[0].length;
          int[][] vis=new int[m][n];
          Queue<int[]> q=new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vis[i][j]=-1;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1){
                    q.add(new int[]{i,j});
                    vis[i][j]=0;
                }
            }
        }
        int ret=-1;
        int[] dx={0,0,1,-1};
        int[] dy={1,-1,0,0};
        while(!q.isEmpty()){
            int[] t=q.poll();
            int a=t[0],b=t[1];
            for (int i = 0; i < 4; i++) {
                int x=dx[i]+a;
                int y=dy[i]+b;
                if(x>=0 && x<m && y>=0 && y<n && vis[x][y]==-1 ){
                    q.add(new int[]{x,y});
                    vis[x][y]=vis[a][b]+1;
                    ret=Math.max(ret,vis[x][y]);
                }
            }
        }
        return ret;
    }
    //组队
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] a1={97,92,0,0,89,82,0,0,0,95,0,0,94,0,0,0,98,93,0,0};
        int[] a2={90,85,0,0,83,86,0,97,0,99,0,0,91,83,0,0,83,87,0,99};
        int[] a3={0,96,0,0,97,0,0,96,89,0,96,0,0,87,98,0,99,92,0,96};
        int[] a4={0,0,0,80,0,0,87,0,0,0,97,93,0,0,97,93,98,96,89,95};
        int[] a5={0,0,93,86,0,0,90,0,0,0,0,98,0,0,98,86,81,98,92,81};
        //在此输入您的代码...
        int ret=0;
        for (int i = 0; i < 20; i++) {
            int sum=0;
            for (int j = 0; j < 20; j++) {
                if(i!=j){
                for (int k = 0; k < 20; k++) {
                    if(j!=k && k!=i){
                    for (int l = 0; l < 20; l++) {
                        if(i!=l && j!=l && k!=l) {
                            for (int m = 0; m < 20; m++) {
                            if(i!=m && j!=m && k!=m && l!=m ){
                                sum=a1[i]+a2[j]+a3[k]+a4[l]+a5[m];
                                ret=Math.max(sum,ret);
                            }
                        }
                    }}
                }}
            }
            }
        }
        System.out.println(ret);
        scan.close();
    }
    //数列求值
    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        BigInteger[] a=new BigInteger[20190325];
        int j;
        a[0]=BigInteger.ONE;a[1]= BigInteger.ONE;a[2]=BigInteger.ONE;a[3]=BigInteger.valueOf(3);
        for ( j = 4; j <=  20190324-1; j++) {
            a[j]=(a[j-1].add(a[j-2]).add(a[j-3])).mod(BigInteger.valueOf(10000));
        }
        System.out.println(a[j-1].toString().substring(Math.max(0, a[j-1].toString().length() - 4)));
        scan.close();
    }
//数的分解（错误）
    public static void main5(String[] args) {
        //下标要正确对应，写的时候，写几个进行测试，插是否正确，取最后几位模几位
        //数组大小直接n+1即可
        int n = 20190324;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10000;
        }
        System.out.println(dp[n]);
    }
    //正确
    public static void main9(String[] args) {
        //在此输入您的代码...
        int count=0;
        for (int i = 1; i < 2019; i++) {
            int sum=0;
            if(fun1(i)){
            for (int j = i+1; j < 2019-i-j; j++) {
                if(fun1(j) && i!=j){
                   int k=2019-i-j;
                   if(k>j && fun1(k)) {count++;}
            }}
        }}
        System.out.println(count);
    }
    public static boolean fun1(int n){
        String tmp=String.valueOf(n);
        if(tmp.contains("2") || tmp.contains("4") ) return false;
        return true;
    }
    public static boolean fun(int n){
        int tmp=0;
        while(n!=0){
            tmp=n%10;
            if(tmp==2 || tmp==4) return false;
            n%=10;
        }
        return true;
    }


}
